//
//  ProblemOffer27.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 27. 二叉树的镜像
 请完成一个函数，输入一个二叉树，该函数输出它的镜像。

 例如输入：
      4
    /   \
   2     7
  / \   / \
 1   3 6   9
 镜像输出：
      4
    /   \
   7     2
  / \   / \
 9   6 3   1

 示例 1：
     输入：root = [4,2,7,1,3,6,9]
     输出：[4,7,2,9,6,3,1]
 限制：
    0 <= 节点个数 <= 1000
 */
@objcMembers class ProblemOffer27: NSObject {
    func solution() {
        let root = TreeNode(4)
        root.left = TreeNode(2)
        root.left?.left = TreeNode(1)
        root.left?.right = TreeNode(3)
        
        root.right = TreeNode(7)
        root.right?.left = TreeNode(6)
        root.right?.right = TreeNode(9)
        
        let mroot = mirrorTreeG(root)
        print(printNodeTree(mroot))
    }
    
    /*
     深度
     思路：就是交换左右节点
     */
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil {
            return nil
        }
        let left = root?.left
        let right = root?.right
        root?.left = mirrorTree(right)
        root?.right = mirrorTree(left)
        
        return root
    }
    
    /*
     广度：
     放入数组中，依次进行处理
     */
    func mirrorTreeG(_ root: TreeNode?) -> TreeNode? {
        var list:[TreeNode?] = [root]
        while list.isEmpty == false {
            let node = list.removeLast()
            
            let left = node?.left
            if left != nil {
                list.append(left)
            }
            let right = node?.right
            if right != nil {
                list.append(right)
            }
            
            node?.left = right
            node?.right = left
            
        }
        return root
    }
    
}
